package com.njupt.Tree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author: wujiaming
 * @CreateTime: 2024/11/19 9:55
 * @Description: 二叉树前序遍历
 * @Version: 1.0
 */


public class PreorderTraversalNoRecursion {


    /**
     * 先序遍历的第一种写法，先访问根节点，然后先将右子树入栈，然后左子树入栈
     * 因为只有这样出栈的时候才是左子树先出栈，然后才是右子树在出栈
     * @param root
     * @return
     */
    public List<Integer> preorderTraversalNoRecursion(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        if(root == null) return result;
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if(node.right != null) stack.push(node.right);
            if(node.left != null) stack.push(node.left);
        }

        return  result;

    }

    /**
     * 非递归遍历的第二种写法
     * 需要一个遍历节点指针，初始指向根节点，
     * 先遍历万所有根节点的左子树，然后遍历万有所根节点的右子树
     * 以根左右的形式入栈
     * @param root
     * @return
     */
    public List<Integer> preorderTraversalNoRecursion1(TreeNode root){
        List<Integer> results = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        if(root == null) return results;
        TreeNode cur = root;

        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                results.add(cur.val);
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            cur = cur.right;
        }
        return results;
    }


    /**
     * 第二种写法的变体，
     * 这种写法与第二种本质上是一样的
     * @param root
     * @return
     */
    public List<Integer> preorderTraversalNoRecursion2(TreeNode root){
        List<Integer> results = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        if(root == null) return results;
        TreeNode cur = root;

        while(cur != null || !stack.isEmpty()){
            if(cur != null){
                results.add(cur.val);
                stack.push(cur);
                cur = cur.left;
            }else {
                cur = stack.pop();
                cur = cur.right;
            }

        }
        return results;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(3);
        root.right = node1;
        node1.left = node2;
        PreorderTraversalNoRecursion test = new PreorderTraversalNoRecursion();
        List<Integer> list = test.preorderTraversalNoRecursion2(root);
        System.out.println(list.toString());
    }
}
